package com.sympsel.Optimal_Algorithm_OA;

import org.junit.Test;

import java.util.*;


public class SlidingWindowDemo {
    public int minSubArrayLen1(int target, int[] nums) {
        // 暴力解法，leetcode超时
        int n = nums.length;
        int min = n;
        for (int i = 0; i < n; i++) {
            int sum = nums[i];
            int j = i + 1;
            while (j < n && sum < target) {
                sum += nums[j++];
            }
            if (sum >= target) {
                min = Math.min(min, j - i);
            }
            // 第一次遍历是整个数组的和, 如果仍然更小则，直接返回0
            // 也可以将min 初始化为 Integer.MAX_VALUE; 然后在算法末尾判断是否仍为初始值
            if (i == 0 && sum < target) {
                return 0;
            }
        }
        return min;
    }

    public int minSubArrayLen2(int target, int[] nums) {
        // 滑动窗口
        int n = nums.length;
        int left = 0, right = 0;
        int sum = 0, len = Integer.MAX_VALUE;
        while (right < n) {
            sum += nums[right++];
            while (sum >= target) {
                len = Math.min(right - left, len);
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    @Test
    public void test1() {
        int[][] nums = {
                {2, 3, 1, 2, 4, 3},
                {1, 4, 4},
                {1, 1, 1, 1, 1, 1, 1, 1},
                {1, 2, 3, 4, 5}
        };
        int[] targets = {7, 4, 11, 15};

//        for (int i = 0; i < nums.length; i++) {
//            System.out.println(minSubArrayLen1(targets[i], nums[i]));
//        }

        for (int i = 0; i < nums.length; i++) {
            System.out.println(minSubArrayLen2(targets[i], nums[i]));
        }
    }

    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0, len = 0;
        while (right < s.length()) {
            char c = s.charAt(right++);
            while (set.contains(c)) {
                set.remove(s.charAt(left));
                left++;
            }

            set.add(c);
            len = Math.max(len, right - left);
        }
        return len;
    }

    public int lengthOfLongestSubstring2(String s) {
        // Set<Character> set = new HashSet<>();
        // int left = 0, right = 0, len = 0;
        // while (right < s.length()) {
        //     char c = s.charAt(right++);
        //     while (set.contains(c)) {
        //         set.remove(s.charAt(left++));
        //     }
        //     set.add(c);
        //     len = Math.max(len, right - left);
        // }
        // return len;
        char[] str = s.toCharArray();

        char[] hash = new char[128];
        int left = 0, right = 0;
        int len = 0;
        while (right < s.length()) {
            hash[str[right]]++;
            while (hash[str[right]] > 1) {
                hash[str[left++]]--;
            }
            len = Math.max(len, right - left + 1);
            right++;
        }
        return len;
    }

    @Test
    public void test2() {
        String[] strs = {"abcabcbb", "bbbbb", "pwwkew", "aab", "dvdf"};
        for (String str : strs) {
            System.out.println(lengthOfLongestSubstring2(str));
        }
    }

    public int longestOnes(int[] nums, int k) {
        int len = 0;
        for (int right = 0, left = 0, zeroCount = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                if (nums[left++] == 0) {
                    zeroCount--;
                }
            }
            len = Math.max(len, right - left + 1);
        }
        return len;
    }

    @Test
    public void test3() {
        int[][] demo = {
                {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0},
                {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}
        };
        int[] ks = {2, 3};
        for (int i = 0; i < demo.length; i++) {
            System.out.println(longestOnes(demo[i], ks[i]));
        }
    }

    public int minOperations(int[] nums, int x) {
        int sumOfNums = 0;
        for (int num : nums) {
            sumOfNums += num;
        }
        int target = sumOfNums - x;
        if (target < 0) {
            return -1;
        }
        int sum = 0, left = 0, right = 0, len = -1, n = nums.length;
        while (right < n) {
            sum += nums[right++];
            while (sum > target) {
                sum -= nums[left++];
            }
            if (sum == target) {
                len = Math.max(len, right - left);
            }
        }
        return len == -1 ? -1 : n - len;
    }

    @Test
    public void test4() {
        int[][] demo = {
                {1, 1, 4, 2, 3},
                {5, 6, 7, 8, 9},
                {3, 2, 20, 1, 1, 3}
        };
        int[] xs = {5, 4, 10};
        for (int i = 0; i < demo.length; i++) {
            System.out.println(minOperations(demo[i], xs[i]));
        }
    }

    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = 0;
        for (int left = 0, right = 0; right < fruits.length; right++) {
            int in = fruits[right];
            map.put(in, map.getOrDefault(in, 0) + 1);
            for (; map.size() > 2; left++) {
                int out = fruits[left];
                map.put(out, map.get(out) - 1);
                if (map.get(out) == 0) {
                    map.remove(out);
                }
            }
            len = Math.max(len, right - left + 1);
        }
        return len;
    }

    @Test
    public void test5() {
        int[][] demo = {
                {1, 2, 1},
                {0, 1, 2, 2},
                {1, 2, 3, 2, 2},
                {3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4}

        };

        int[] result = {3, 3, 4, 5};
        for (int i = 0; i < demo.length; i++) {
            System.out.println(totalFruit(demo[i]) == result[i]);
        }
    }

    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int len1 = s.length(), len2 = p.length();
        if (len1 < len2) {
            return ret;
        }
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();

        int i = 0;
        while (i < len2) {
            char c1 = s.charAt(i);
            char c2 = p.charAt(i);
            map1.put(c1, map1.getOrDefault(c1, 0) + 1);
            map2.put(c2, map2.getOrDefault(c2, 0) + 1);
            i++;
        }
        if (map1.equals(map2)) {
            ret.add(0);
        }
        while (i < len1) {
            char c1 = s.charAt(i - len2);
            char c2 = s.charAt(i);
            map1.put(c1, map1.get(c1) - 1);
            map1.put(c2, map1.getOrDefault(c2, 0) + 1);
            if (map1.get(c1) == 0) {
                map1.remove(c1);
            }
            if (map1.equals(map2)) {
                ret.add(i - len2 + 1);
            }
            i++;
        }
        return ret;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int len1 = s.length(), len2 = p.length();
        if (len1 < len2) {
            return ret;
        }
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        int i = 0;
        while (i < len2) {
            map1[s.charAt(i) - 'a']++;
            map2[p.charAt(i) - 'a']++;
            i++;
        }
        if (Arrays.equals(map1, map2)) {
            ret.add(0);
        }
        while (i < len1) {
            map1[s.charAt(i - len2) - 'a']--;
            map1[s.charAt(i) - 'a']++;
            if (Arrays.equals(map1, map2)) {
                ret.add(i - len2 + 1);
            }
            i++;
        }
        return ret;
    }

    public List<Integer> findAnagrams3(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int len1 = s.length(), len2 = p.length();
        if (len1 < len2) {
            return ret;
        }
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        int count = 0;
        for (int i = 0; i < len2; i++) {
            map2[p.charAt(i) - 'a']++;
        }
        for (int i = 0; i < len2; i++) {
            char c = s.charAt(i);
            map1[c - 'a']++;
            if (map1[c - 'a'] <= map2[c - 'a']) {
                count++;
            }
        }

        if (count == len2) {
            ret.add(0);
        }

        for (int i = len2; i < len1; i++) {
            char c1 = s.charAt(i - len2);
            char c2 = s.charAt(i);

            if (map1[c1 - 'a']-- <= map2[c1 - 'a']) {
                count--;
            }
            if (++map1[c2 - 'a'] <= map2[c2 - 'a']) {
                count++;
            }

            if (count == len2) {
                ret.add(i - len2 + 1);
            }
        }
        return ret;
    }

    @Test
    public void test6() {
        String str = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams1(str, p));
        System.out.println(findAnagrams2(str, p));
        System.out.println(findAnagrams3(str, p));
    }

    public List<Integer> findSubstring(String s, String[] words) {
        int step = words[0].length();
        int wordNum = words.length;
        int len = s.length();
        List<Integer> ret = new ArrayList<>();
        if (wordNum * step > len) {
            return ret;
        }
        Map<String, Integer> standard = new HashMap<>();
        for (String word : words) {
            standard.put(word, standard.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i < step; i++) {
            int count = 0;
            Map<String, Integer> map = new HashMap<>();
            // 初始化窗口
            for (int j = i; j < Math.min(len - step + 1, wordNum * step + i); j += step) {
                String word = s.substring(j, j + step);
                map.put(word, map.getOrDefault(word, 0) + 1);
                if (standard.containsKey(word) && map.get(word) <= standard.get(word)) {
                    count++;
                }
            }

            if (count == wordNum) {
                ret.add(i);
            }

            // 滑动窗口
            for (int j = wordNum * step + i; j <= len - step; j += step) {
                String wordLeft = s.substring(j - step * wordNum, j - step * (wordNum - 1));
                if (standard.containsKey(wordLeft) && map.get(wordLeft) <= standard.get(wordLeft)) {
                    count--;
                }
                map.put(wordLeft, map.get(wordLeft) - 1);

                if (map.get(wordLeft) == 0) {
                    map.remove(wordLeft);
                }

                String wordRight = s.substring(j, j + step);
                map.put(wordRight, map.getOrDefault(wordRight, 0) + 1);
                if (standard.containsKey(wordRight) && map.get(wordRight) <= standard.get(wordRight)) {
                    count++;
                }

                if (count == wordNum) {
                    ret.add(j - (wordNum - 1) * step);
                }
            }
        }
        return ret;
    }

    @Test
    public void test7() {
        String s1 = "barfoothefoobarman";
        String[] words = {"foo", "bar"};
        String s2 = "barfoofoobarthefoobarman";
        String[] words2 = {"bar", "foo", "the"};
        String s3 = "wordgoodgoodgoodbestword";
        String[] words3 = {"word", "good", "best", "good"};
        String s4 = "ababababab";
        String[] words4 = {"ababa", "babab"};
        System.out.println(findSubstring(s1, words));
        System.out.println(findSubstring(s2, words2));
        System.out.println(findSubstring(s3, words3));
        System.out.println(findSubstring(s4, words4));
    }

    /**
     * 最小覆盖子串 - 能写出这样的代码也是神人了，写完立马就看不懂了，但是Leetcode能过
     */
    public String minWindow1(String s, String t) {
        Map<Character, Integer> tarMap = new HashMap<>();
        int tarLen = t.length(), len = s.length();
        if (tarLen > len) {
            return "";
        }
        int minLen = Integer.MAX_VALUE;
        // 初始化目标哈希表
        for (int i = 0; i < tarLen; i++) {
            char key = t.charAt(i);
            tarMap.put(key, tarMap.getOrDefault(key, 0) + 1);
        }
        int left = 0;
        int begin = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int right = 0, count = 0; right < len; right++) {
            char rightKey = s.charAt(right);
            // 如果匹配到目标字符，则更新对应字符的个数
            if (tarMap.containsKey(rightKey)) {
                map.put(rightKey, map.getOrDefault(rightKey, 0) + 1);
            }
            // flag作用：当left指向字符在目标字符哈希表中的个数大于目标字符的个数时，再次减到对应数量后续不会重复累加count值（只有在小于时才应该累加），如果直接使用count--抵消不知道为什么会出bug
            boolean flag = true;
            while (map.getOrDefault(s.charAt(left), 0) > tarMap.getOrDefault(s.charAt(left), 0)) {
                char leftKey = s.charAt(left);
                flag = true;
                if (map.containsKey(leftKey)) {
                    map.put(leftKey, map.get(leftKey) - 1);
                    if (map.get(leftKey) == 0) {
                        map.remove(leftKey);
                    }
                    flag = false;
                }
                do {
                    left++;
                } while (!map.containsKey(s.charAt(left)));
            }

            if (flag && tarMap.containsKey(rightKey) && Objects.equals(map.getOrDefault(rightKey, 0), tarMap.get(rightKey))) {
                count++;
            }

            while (!tarMap.containsKey(s.charAt(left)) && left < right) {
                left++;
            }

            if (count == tarMap.size() && right - left + 1 < minLen) {
                begin = left;
                minLen = right - left + 1;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(begin, begin + minLen);
    }

    // 使用标准的滑动窗口解法
    public String minWindow2(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int minLen = Integer.MAX_VALUE, begin = 0, valid = 0, len = s.length();
        Map<Character, Integer> target = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            target.put(t.charAt(i), target.getOrDefault(t.charAt(i), 0) + 1);
        }

        for (int right = 0, left = 0; right < len; right++) {
            char in = s.charAt(right);
            if (target.containsKey(in)) {
                window.put(in, window.getOrDefault(in, 0) + 1);
                if (Objects.equals(window.get(in), target.get(in))) {
                    valid++;
                }
            }

            while (valid == target.size()) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    begin = left;
                }
                char out = s.charAt(left);
                if (target.containsKey(out)) {
                    if (Objects.equals(window.get(out), target.get(out))) {
                        valid--;
                    }
                    window.put(out, window.get(out) - 1);
                    if (window.get(out) == 0) {
                        window.remove(out);
                    }
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(begin, begin + minLen);
    }

    // 使用数组模拟的哈希表
    public String minWindow3(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int minLen = Integer.MAX_VALUE, begin = 0, valid = 0, len = s.length();

        int[] target = new int[128];
        int[] window = new int[128];
        for (int i = 0; i < t.length(); i++) {
            target[t.charAt(i)]++;
        }
        // 获取目标字符种类数
        int type = 0;
        for (int i = 0; i < 128; i++) {
            if (target[i] != 0) {
                type++;
            }
        }

        for (int right = 0, left = 0; right < len; right++) {
            char in = s.charAt(right);

            if (target[in] > 0) {
                window[in]++;
                if (window[in] == target[in]) {
                    valid++;
                }
            }

            while (valid == type) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    begin = left;
                }
                char out = s.charAt(left);
                if (target[out] > 0) {
                    if (window[out] == target[out]) {
                        valid--;
                    }
                    window[out]--;
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(begin, begin + minLen);
    }

    interface MinWindowCallback {
        String minWindow(String s, String t);
    }


    void minWindowDemo(MinWindowCallback callback, String s, String t) {
        System.out.println(callback.minWindow(s, t));
    }

    @Test
    public void test8() {
        String[] testCases = new String[]{
                "ADOBECODEBANC",
                "a",
                "a",
                "ab",
                "a",
                "aa",
                "cabwefgewcwaefgcf"
        };
        String [] targets = new String[]{
                "ABC",
                "a",
                "aa",
                "b",
                "b",
                "aa",
                "cae"
        };
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("测试用例：" + testCases[i] + " " + targets[i]);
            minWindowDemo(this::minWindow1, testCases[i], targets[i]);
            minWindowDemo(this::minWindow2, testCases[i], targets[i]);
            minWindowDemo(this::minWindow3, testCases[i], targets[i]);
        }
    }
}
